package com.cdream.basic.algorithm.leetcode.stack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author cdream
 * @date 6/26/21
 */
public class Question94 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        treeNode.right = treeNode1;
        treeNode1.left = treeNode2;
        new Question94().inorderTraversal(treeNode);

    }
    private List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            if(root.right!=null){
                root = root.right;
            }else{
                root = null;
            }
        }
        return res;
    }
}
